import java.util.*;
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;

// Apply DFS to find all the possible paths from the 'o' on the edge

public class region {
  public static void dfs(int rowIndex, int colIndex, int rowDim, int colDim, char[][] board) {
    if (board[rowIndex][colIndex] == 'O') {
      board[rowIndex][colIndex] = 'C';  // checked
    } else if (board[rowIndex][colIndex] == 'X' || board[rowIndex][colIndex] == 'C') {
      return;
    }
    if (rowIndex - 1 > 0) {
      dfs(rowIndex - 1, colIndex, rowDim, colDim, board);
    }
    if (rowIndex + 1 < rowDim) {
      dfs(rowIndex + 1, colIndex, rowDim, colDim, board);
    }
    if (colIndex - 1 > 0) {
      dfs(rowIndex, colIndex - 1, rowDim, colDim, board);
    }
    if (colIndex + 1 < colDim) {
      dfs(rowIndex, colIndex + 1, rowDim, colDim, board);
    }
  }

  public static void solve(char[][] board) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int rowDim = board.length;
    if (rowDim == 0) {
      return;
    }
    int colDim = board[0].length;
    // apply dfs on the exterior boarder
    // West and East
    for (int i = 0; i < rowDim; i++) {
      dfs(i, 0, rowDim, colDim, board);
      dfs(i, colDim - 1, rowDim, colDim, board);
    }
    // North and South
    for (int j = 1; j < colDim - 1; j++) {
      dfs(0, j, rowDim, colDim, board);
      dfs(rowDim - 1, j, rowDim, colDim, board);
    }
    
    // update the board again, turn all the 'o' as 'x', and 'c' as 'o'
    for (int i = 0; i < rowDim; i++) {
      for (int j = 0; j < colDim; j++) {
        if (board[i][j] == 'O') {
          board[i][j] = 'X';
        }
        if (board[i][j] == 'C') {
          board[i][j] = 'O';
        }
      }
    }
  }
  
  public static void display(char[][] board, int totalRow) {
    for (int i = 0; i < totalRow; i++) {
      System.out.println(new String(board[i]));
    }
  }
  
  public static void main(String[] args) {
    // From a file
    String FILENAME = "D:\\Snoopy\\Programming\\Interview\\Java\\LeetCode\\surrounded_region\\test.txt";
    Path path = Paths.get(FILENAME);
    try {
      Scanner scanner =  new Scanner(path);
      if (scanner.hasNextLine()){
        String line = scanner.next();
        String [] splitedLine = line.substring(2, line.length() - 2).split("\",\"");
        System.out.println("Row number is " + splitedLine.length + "; Column number is " + splitedLine[0].length());
        int rowLen = splitedLine.length, colLen = splitedLine[0].length();
        /*for (String l : splitedLine) {
          System.out.println(l);
        }*/
        char [][] board = new char[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
          board[i] = splitedLine[i].toCharArray();
        }
        System.out.println("\nThe original board is :");
        display(board, rowLen);
        solve(board);
        System.out.println("\nThe updated board is :");
        display(board, rowLen);
      }
    } catch(IOException e) {
      System.out.println("IO Error: file not exist!!!");
    }
    // From standard input
    /*
    Scanner scanner = new Scanner(System.in);
    int rowLen = scanner.nextInt(), colLen = scanner.nextInt();
    // System.out.println("Row is " + row + "; Column is " + col);
    char [][] board = new char[rowLen][colLen];
    int curRow = 0;
    while (curRow < rowLen && scanner.hasNext()) {
      String curLine = scanner.next();
      board[curRow] = curLine.toCharArray();
      // System.out.println("Row " + curRow + " is: " + new String(board[curRow]));
      curRow++;
    }
    
    System.out.println("\nThe original board is :");
    display(board, rowLen);
    solve(board);
    System.out.println("\nThe updated board is :");
    display(board, rowLen);
    */
  }
}